COMMENT ⊗   VALID 00012 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	%folio 196 galley 1 (C) Addison-Wesley 1978	-
C00015 00003	%folio 198 galley 2 (C) Addison-Wesley 1978	-
C00026 00004	%folio 201 galley 3 (C) Addison-Wesley 1978	-
C00038 00005	%folio 204 galley 4 (C) Addison-Wesley 1978	-
C00052 00006	%folio 206 galley 5 (C) Addison-Wesley 1978	-
C00066 00007	%folio 209 galley 6 (C) Addison-Wesley 1978	-
C00079 00008	%folio 212 galley 7 (C) Addison-Wesley 1978	-
C00087 00009	%folio 214 galley 8 (C) Addison-Wesley 1978	-
C00100 00010	%folio 216 galley 9 (C) Addison-Wesley 1978	-
C00114 00011	%folio 220 galley 10 (C) Addison-Wesley 1978	-
C00124 00012	
C00125 ENDMK
C⊗;
%folio 196 galley 1 (C) Addison-Wesley 1978	-
|newtype W58320---Computer Programming\quad (Knuth/Addison-Wesley)\quad
f. 196\quad ch. 3\quad g. 1d
$$\quad First it is convenient to generalize Definition A, since
the limit appearing there does not exist for all sequences.
Let us define
$$\sqrt{Pr}\biglp $S(n)\bigrp = \mathop{$lim sup↓{|raise2 $n→∞}
\biglp \nu (n)/n\bigrp \qquad$ Pr\biglp $S(n)\bigrp = \mathop{$lim
inf↓{|raise2 $n→∞} \biglp \nu (n)/n\bigrp .\eqno (7)$
|qctr \9skip Then Pr|newtype$ (S(n)\bigrp $, if it exists, is
the common value of Pr\biglp $S(n)|newtype )$ and \sqrt{Pr}\biglp
$S(n)\bigrp $.

We have seen that a $k$-distributed $[0,1)$ sequence leads to
a $k$-distributed $b$-ary sequence, if $U$ is replaced by \lfloor
$bU\rfloor $. Our first theorem shows that a converse result
is true:

\thbegin Theorem A. \xskip} {\sl Let \langle \lfloor b↓jU↓n3\rangle
= U↓0$, $U↓1$, $U↓2$, $\ldots$ be a $[0,1)$ sequence. If the sequence}
$$\langle \lfloor b$↓jU↓n\rfloor \rangle = 8b↓jU↓0\rfloor ,
\lfloor b↓jU↓1\rfloor , \lfloor b↓jU↓2\rfloor , . . $.
|qctr \9skip is a k-distributed b$↓j-ary sequence for all b↓j
in an infinite sequence of integers $1 < b↓1 < b↓2 < b↓3 < \cdotss$,
then the original sequence $\langle U↓n\rangle$ is $k$-distributed.}

|qleft \12skip \quad As an example of this theorem, suppose
that $b↓j = 2↑j$. The sequence \lfloor $2↑jU↓0\rfloor , \lfloor
2↑jU↓1\rfloor , . . $. is essentially the sequence of the first
$j$ bits of the binary representations of $U↓0$, $U↓1$, $\ldotss\,$.
If all these integer sequences are $k$-distributed, in the sense
of Definition D, the real-valued sequence $U↓0, U↓1, . . $.
must also be $k$-distributed in the sense of Definition B.

|qleft \12skip {\sl Proof of Theorem A. \xskip} If the sequence
$\lfloor bU↓0\rfloor , \lfloor bU↓1\rfloor , . . $. is $k$-distributed,
it follows by the addition of probabilities that Eq.\ (5) holds
whenever each $u↓j$ and $v↓j$ is a rational number with denominator
$b$. Now let $u↓j, v↓j$ be any real numbers, and let $u↑{↑\prime}↓{j}
≤ U↓J < U↑{↑\prime}↓{j} + 1/b, v↑{↑\prime}↓{j} ≤ v↓j < v↑{↑\prime}↓{j}
+ 1/b$.
|qctr \9skip Let $S(n)$ be the statement that $u↓1 ≤ U↓n < v↓1$,
$\ldotss$, $u↓k ≤ U↓{n+k-1} < v↓k$. We have
$$Pr|newtype$ (S(n)\bigrp ≤$ Pr\left($u↑{↑\prime}↓{1} ≤ U↓n
< v↑{↑\prime}↓{1} + {1\over b} , \ldotss , u↑{↑\prime}↓{k} ≤
U↓{n+k-1} < v↑{↑\prime}↓{k} + {1\over b}}$

|qleft \4skip = \left(v↑{↑\prime}↓{1} - u↑{↑\prime}↓{1} + ${1\over
b}$} \ldotsm \left(v↑{↑\prime}↓{k} - u↑{↑\prime}↓{k} + ${1\over
b}$};
|qright \6skip Pr\biglp $S(n)\bigrp ≥$ Pr\left($u↑{↑\prime}↓{1}
+ {1\over b} ≤ U↓n < v↑{↑\prime}↓{1}, \ldotss , U↑{↑\prime}↓{k}
+ {1\over b} ≤ U↓{n+k-1} < v↑{↑\prime}↓{k}}$

|qleft \4skip = \left(v↑{↑\prime}↓{1} - u↑{↑\prime}↓{1} - ${1\over
b}$} \ldotsm \left(v↑{↑\prime}↓{k} - u↑{↑\prime}↓{k} - ${1\over
b}$}.
|qright \9skip Now |($v↑{↑\prime}↓{j} - u↑{↑\prime}↓{j} \pm
1/b) - (v↓j - u↓j)| ≤ 2/b$; since our inequalities hold for
all $b = b↓j$, and since $b↓j → ∞$ as $j → ∞$, we have
$$($v↓1 - u↓1) \ldotsm (v↓k - u↓k) ≤$ Pr\biglp $S(n)\bigrp ≤$
Pr\biglp $S(n)|newtype ) ≤ (v↓1 - u↓1) \ldotsm (v↓k - u↓k)$.

|qleft \9skip \quad The next theorem is our main tool for proving
things about $k$-distributed sequences.

\thbegin Theorem B. {\sl Let \langle U↓n\rangle
be a k-distributed $[0,1)$ sequence, and let f(x↓1, x↓2, \ldotss
, x↓k) be a Riemann-integrable function of k variables{\sl ;}
then}
$$\mathop{lim↓{$|raise2 n→∞} {1\over n} \sum ↓{0≤j<n} f(U↓j,
U↓{j+1}, \ldotss , U↓{j+k-1})$

|qleft \4skip = \int ↑{1}↓{0} \ldotsm \int ↑{1}↓{0} f(x$↓1, x↓2,
\ldotss , x↓k)\, dx↓1 \ldotsm dx↓k.\quad (8)$
|qright \9skip Proof. \xskip The definition of a $k$-distributed
sequence states that this result is true in the special case
that
$$$f(x↓1, \ldotss , x↓k) = \left\{{1,\qquad \atop 0,\qquad }{$if\qquad
$u↓1 ≤ x↓1 < v↓1, \ldotss , u↓k ≤ x↓k < v↓k;\atop \quad }\eqno
(9)$
|qctr \9skip Therefore Eq.\ (8) is true whenever $f = a↓1f↓1
+ a↓2f↓2 + \cdots + a↓mf↓m$ and when each $f↓j$ is a function
of type (9); in otherwords, Eq.\ (8) holds whenever $f$ is a
``step-function;; obtained by (i) partitioning the unit $k$-dimensional
cube into subcells whose faces are parallel to the coordinate
axes, and (ii) assigning a constant value to $f$ on each subcell.

Now let $f$ be any Riemann-integrable function. If $\epsilon$
is any positive number, we know (by the definition of Riemann-integrability)
that there exist step functions $f$ and $|spose ??f$ such that
$f(x↓1, \ldotss , x↓k) ≤ f(x↓1, \ldotss , x↓k) ≤ |spose ??f(x↓1,
\ldotss , x↓k)$, and such that the difference of the integrals
of $f$ and $|spose ??f$ is less than $\epsilon $. Since Eq.\
(8) holds for $f$ and $|spose ??f$, and since
$$${1\over n}$ \sum ↓{0≤j<n} f(U$↓j, \ldotss , U↓{j+k-1}) ≤ {1\over
n} \sum ↓{0≤j<n} f(U↓j, \ldotss , U↓{j+k-1})$
 |qctr \4skip ≤ ${1\over n}$ \sum ↓{0≤j<n} |spose ??f(U$↓j, \ldotss
, U↓{j+k-1})$,
|qctr \9skip we conclude Eq.\ (8) is true also for $f$.

|qleft \12skip \quad As the first application of this theorem,
consider the {\sl permutation test} described in Section 3.3.2.
Let $(p↓1, p↓2, \ldotss , p↓k)$ be any permutation of the numbers
$\{1, 2, \ldotss , k\}$; we want to show that
$$Pr($U↓{n+p}|infinf 1↓{-1} < U↓{n+p}|infinf 2↓{-1}) = 1/k!.\eqno
(10)$
|qctr \9skip To prove this, assume that the sequence \langle
$U↓n\rangle$ is $k$-distributed, and let
$$$f(x↓1, \ldotss , x↓k) = {1,\qquad \atop 0,\qquad }{$if\qquad
$x↓p|infinf 1 ≤ x↓p|infinf 2 ≤ \cdots ≤ x↓p|infinf k\atop \quad
}$
|qctr \9skip We have
$$Pr($U↓{n+p}|infinf 1↓{-1} < U↓{n+p}|infinf 2↓{-1} < \cdots
< U↓{n+p}|infinf k↓{-1})$

|qleft \4skip |tab = \int ↑{1}↓{0} \ldotsm \int ↑{1}↓{0} f(x$↓1,
\ldotss , x↓k) dx↓1 \ldotsm dx↓k⊗\4skip ⊗= \int ↑{1}↓{0} dx↓p|infinf
k \int ↑{x↓p|infinf k}↓{0} \ldotsm \int ↑{x↓p|infinf 3}↓{0} dx↓p|infinf
2 \int ↑{x↓p|infinf 2}↓{0} dx↓p|infinf 1 = {1\over k!} .\cr

\thbegin Corollary P. {\sl If a $[0,1)$ sequence
is k-distributed, it satisfies the permutation test of order
k, in the sense of Eq.\ (10).}

|qleft \12skip \quad We can also show that the {\sl serial correlation
test} is satisfied:

\thbegin Corollary S. {\sl If a $[0,1)$ sequence is (k
+ 1)-distributed, the serial correlation coefficient between
U↓n and U↓{n+k} tends to zero{\sl :}
|qleft }\9skip \mathop{lim↓{|raise2 $n→∞} {{1\over n} \sum U↓jU↓{j+k}
- \left({1\over n} \sum U↓j}\left({1\over n} \sum U↓{j+k}}??1\sqrt{2\left({1\over
n} \sum U↑{2}↓{j} - \left({1\over n} \sum U↓j}↑2}\left({1\over
n} \sum U↑{2}↓{j+k} - \left({1\over n} \sum U↓{j+k}}↑2|newtype
}|newtype ???? = 0$.
|qctr \9skip (All summations here are for 0 ≤ $j < n.)$

|qleft \12skip Proof. \xskip By Theorem B, the quantities
$$${1\over n}$ \sum U$↓jU↓{j+k},\qquad {1\over n} \sum U↑{2}↓{j},\qquad
{1\over n} \sum U↑{2}↓{j+k},\qquad {1\over n} \sum U↓j,\qquad
{1\over n} \sum U↓$
{j+k}|qctr \9skip tend to the respective limits ${1\over 4}$,
${1\over 3}$, ${1\over 3}$, ${1\over 2}$, ${1\over 2}$ as $n
→ ∞$.
|qleft u|newtype W58320---Computer Programming\quad (Knuth/Addis
%folio 198 galley 2 (C) Addison-Wesley 1978	-
\yyskip Let us now consider some slightly more general distribution
properties of sequences. We have defined the notion of $k$-distribution
by considering all of the adjacent $k$-tuples; for example, a sequence
is 2-distributed if and only if the points
$$(U↓0, U↓1),\qquad (U↓1, U↓2),\qquad (U↓2, U↓3),\qquad
(U↓3, U↓4),\qquad (U↓4, U↓5),\qquad\ldots$$
are equidistributed in the unit square. It is quite
possible, however, that the alternate pairs of points $(U↓1,
U↓2)$, $(U↓3, U↓4)$, $(U↓5, U↓6)$, $\ldots$ are not themselves equidistributed;
if the density of points $(U↓{2n-1}, U↓{2n})$ is deficient in
some area, the other points $(U↓{2n}, U↓{2n+1})$ might compensate.
For example, the periodic binary sequence
$$\langle X↓n\rangle = 0, 0, 0, 1,\, 0, 0, 0, 1,\,1,
1, 0, 1,\, 1, 1, 0, 1,\, 0, 0, 0, 1,\, \ldotss ,\eqno(11)$$
with a period of length 16, is seen to be 3-distributed;
yet the sequence of even-numbered elements $\langle X↓{2n}\rangle
= 0$, 0, 0, 0, 1, 0, 1, 0, $\ldots$ has three times as many zeros
as ones, while the subsequence of odd-numbered elements $\langle
X↓{2n+1}\rangle = 0$, 1, 0, 1, 1, 1, 1, 1, $\ldots$ has three
times as many ones as zeros.

If a sequence \langle $U↓n\rangle$ is $∞$-distributed, the example
above shows that it is not at all obvious that the subsequence
of alternate terms \langle $U↓{2n}\rangle = U↓0, U↓2, U↓4, U↓6,
. . $. is $∞$-distributed or even 1-distributed. But we shall
see that $\langle U↓{2n}\rangle$ is, in fact, $∞$-distributed,
and much more is also true.

\thbegin Definition E. {\sl A $[0,1)$ sequence
\langle U↓n\rangle is said to be (m, k)-distributed if$
$$Pr($u↓1 ≤ U↓{mn+j} < v↓1, u↓2 ≤ U↓{mn+j+1} < v↓2, \ldotss ,
u↓k ≤ U↓{mn+j+k-1} < v↓k)$

|qleft \4skip = (v$↓1 - u↓1) \ldotsm (v↓k - u↓k)$
|qright \9skip for all choices of real numbers u$↓r, v↓r with
0 ≤ u↓r < v↓r ≤ 1 for 1 ≤ r ≤ k, and for all integers j with
0 ≤ j < m$.

|qleft \12skip Thus a $k$-distributed sequence is the special
case $m = 1$ in Definition E; the case $m = 2$ means that the
$k$-tuples in even positions must have the same density as the
$k$-tuples in odd positions, etc.

Several properties of Definition E are obvious:
$$\quad $An (m, k)-distributed sequence is (m, k)-distributed
for 1 ≤ \kappa ≤ k.\eqno (12)$

|qleft \6skip \quad An (m, k)-distributed sequence is (d, k)-distributed
for all divisors\eqno (13)
|qleft \qquad \quad d of m.

|qleft \9skip We can define the concept of an $(m, k)$-distributed
$b$-ary sequence, as in Definition D; and the proof of Theorem
A remains valid for $(m, k)$-distributed sequences.

The next theorem, which is in many ways rather surprising, shows
that the property of being $∞$-distributed is very strong indeed,
much stronger than we imagined it to be when we first considered
the definition of the concept.

\thbegin Theorem C {\rm(Ivan Niven and H. S. Zuckerman)}.
{\sl An $∞$-distributed sequence is $(m, k)$-distributed for all positive
integers $m$ and $k$.}

|qleft \12skip Proof. \xskip It suffices to prove the theorem
for $b$-ary sequences, by using the generalization of Theorem
A just mentioned. Furthermore, we may assume that $m = k:$ for,
by (12) and (13), the sequence will be $(m, k)$-distributed
if it is $(mk, mk)$-distributed.

So we will prove that {\sl any $∞$-distributed b-ary sequence
X↓0, X↓1, . . . is (m, m)-distributed for all positive integers
m.} Our proof is a simplification of the proof given by Niven
and Zuckerman in {\sl Pacific J. Math.\ \bf 1}
(1951), 103--109.

The theorem is proved by making use of an important idea which
is useful in so many mathematical arguments: ``If the sum of
$m$ quantities and the sum of their squares are both consistent
with the hypothesis that the $m$ quantities are equal, that
hypothesis is true.'' In a strong form, this principle may be
stated as follows:

\thbegin Lemma E. {\sl Given $m$ sequences of numbers $\langle
y↓{jn}\rangle = y↓{j0}$, $y↓{j1}$, $y↓{j2}$, $\ldots$ for $1 ≤ j ≤ m$,
suppose that
$$\quad \mathop{lim↓{|raise2 $n→∞} (y↓{1n} + y↓{2n} + \cdots
+ y↓{mn}) |tab = mα, ⊗\-6skip (14)⊗\-6skip \hfill \mathop{$lim
sup↓{|raise2 $n→∞} (y↑{2}↓{1n} + y↑{2}↓{2n} + \cdots + y↑{2}↓{mn})
⊗≤ mα↑2.\cr
\9skip Then for each j$, lim$↓{n|}¬M↓|¬X y↓{jn} exists and equals
α$.

|qleft \12skip \quad An incredibly simple proof of this lemma
is given in exercise 9.

|qleft \12skip \quad Now to continue our proof of Theorem C.
Let $x = x↓1x↓2 \ldotsm x↓m$ be a $b$-ary number, and say that
{\sl x occurs} at position $p$ of the sequence if $X↓{p-m+1}X↓{p-m+2}
\ldotsm X↓p = x$. Let $\nu ↓j(n)$ be the number of occurrences
of $x$ at position $p$ when $p < n$ and $p$ mod $m = j$. Let
$y↓{jn} = \nu ↓j(n)/n$; we wish to prove that
$$\mathop{lim↓{|raise2 $n→∞} y↓{jn} = 1/mb↑m.\eqno (15)$
|qctr \9skip \quad First we know that
$$\mathop{lim↓{|raise2 $n→∞} (y↓{0n} + y↓{1n} + \cdots + y↓{(m-1)n})
= 1/b↑m,\eqno (16)$
|qctr \9skip since the sequence is $m$-distributed. By Lemma
E and Eq.\ (16), the theorem will be proved if we can show that
$$\mathop{lim sup↓{|raise2 $n→∞} (y↑{2}↓{0n} + y↑{2}↓{1n} +
\cdots + y↑{2}↓{(m-1)n}) ≤ 1/mb↑{2m}.\eqno (17)$
|qctr \9skip \quad This inequality is not obvious yet; some
rather delicate maneuvering is necessary before we can prove
it. Let $q$ be a multiple of $m$, and consider
$$$C(n) = \sum ↓{0≤j<m}\left({\nu ↓j(n) - \nu ↓j(n - q)\atop
2}}.\eqno (18)$
|qctr \9skip This is the number of pairs of occurrences of $x$
in positions $p↓1, p↓2$ with $n - q ≤ p↓1 < p↓2 < n$ and with
$p↓2 - p↓1$ a multiple of $m$. Consider now the sum
$$$S↓N = \sum ↓{1≤n≤N+q} C(n).\eqno (19)$
|qctr \9skip Each pair of occurrences of $x$ in positions $p↓1,
p↓2$ with $p↓1 < p↓2 < p↓1 + q, p↓2 - p↓1$ a multiple of $m$,
and $p↓1 ≤ N$, is counted $p↓1 + q - p↓2$ times in the total
$S↓N$ (namely, when $p↓2 < n ≤ p↓1 + q)$; and the pairs of such
occurrences with $N < p↓1 < p↓2 < N + q$ are counted $N + q
- p↓2$ times.

Let $d↓t(n)$ be the number of pairs of oc urrences of $x$ in
positions $p↓1, p↓2$ with $p↓1 + t = p↓2 < n$. The analysis
above shows that
$$$\sum ↓{0<t<q/m} (q - mt) d↓{mt}(N + q) ≥ S↓N ≥ \sum ↓{0<t<q/m
(q - mt) d↓{mt}(N).\eqno (20)$
|qctr \9skip Since the original sequence is $q$-distributed,
$$\mathop{lim}|raise2 $N→∞?? {1\over N} d↓{mt}(N) = 1/b↑{2m}\eqno
(21)$
|qctr \9skip for all $o < t < q/m$, and therefore by (20)

|qleft \9skip |tab \mathop{lim↓{$|raise2 N→∞} {S↓N\over N} =\sum
↓{0<t<q/m}(q - mt)/b↑{2m}⊗\4skip = q(q - m)/2mb↑{2m}.\eqno (22)\cr
\9skip$ This fact will prove the theorem, after some manipulation.
|qleft u??????|newtype W58320---Compu
%folio 201 galley 3 (C) Addison-Wesley 1978	-
ter Programming\quad (Knuth/Addison-Wesley)\quad f. 201\quad
ch. 3\quad g. 3d
$$\quad By Definition,
$$$2S↓N = \sum ↓{1≤n≤N+q} \sum ↓{0≤j<m} \biglp (\nu ↓j(n) -
\nu ↓j(n - q))↑2 - (\nu ↓j(n) - \nu ↓j(n - q))\bigrp $,
|qctr \9skip and we can remove the unsquared terms by applying
(16) to get
$$\3skip \mathop{lim↓{|raise2 $N→∞} {T↓N\over N} = q(q - m)/mb↑{2m}
+ q/b↑m,\eqno (23)$
|qctr \3skip where
|qleft $T↓N = \sum ↓{1≤n≤N+q} \sum ↓{0≤j<m} \biglp \nu ↓j(n)
- \nu ↓j(n - q)\bigrp ↑2$.
|qctr \9skip \quad Using the inequality
$$${1\over r}$\left(\sum ↓{1≤j≤r}a$↓j}↑2 ≤ \sum ↓{1≤j≤r} a↑{2}↓{j}$
|qctr \9skip (cf.\ exercise 1.2.3--30), we find that
$$\mathop{lim sup↓{|raise2 $N→∞} \sum ↓{0≤j<m} {1\over N(N +
q)} \left(\sum ↓{1≤n≤N+q}(\nu ↓j(n) - \nu ↓j(n - q)\bigrp }↑$

|qleft 2\2skip ≤ q(q - m)/mb$↑{2m} + q/b↑m.\quad (24)$
|qright \6skip We also have
$$$q\nu ↓j(N) ≤ \sum ↓{N<n≤N+q}\nu ↓j(n) = \sum ↓{1≤n≤N+q}\biglp
\nu ↓j(n) - \nu ↓j(n - q)\bigrp ≤ q\nu ↓j(N + q)$,
|qctr \9skip and putting this into (24) gives
$$\mathop{lim sup↓{|raise2 $N→∞} \sum ↓{0≤j<m}\biglp \nu ↓j(N)/N\bigrp
↑2 ≤ (q - m)/qmb↑{2m} + 1/qb↑m.\eqno (25)$
|qctr \9skip This formula has been proved whenever $q$ is a
multiple of $m$, and if we let $q → ∞$ we obtain (17), completing
the proof.

For a possibly simpler proof, see J. W. S. Cassels, {\sl Pacific
J. Math.\ \bf 2} (1952), 555--557.

|qleft \12skip \quad Exercises 29 and 30 illustrate the nontriviality
of this theorem, and they also illustrate the fact, indicated
in (25), that a $q$-distributed sequence will have probabilities
deviating from the true $(m, m)$-distribution probabilities
by essentially 1/\sqrt{$q}$ at most. The full hypothesis of
$∞$-distribution is necessary for the proof of the theorem.

As a result of Theorem C, we can prove that an $∞$-distributed
sequence passes the serial test, the ``maximum of $t$'' test,
and the tests on subsequences mentioned in Section 3.3.2. It
is not hard to show that the gap test, the poker test, and the
run test are also satisfied (see exercises 12 through 14); the
coupon collector's test is considerably more difficult to deal
with, but it too is satisfied (see exercises 15 and 16).

|qleft \12skip \quad The existence of $∞$-distributed sequences
of a rather simple type is guaranteed by the next theorem.

\thbegin Theorem F  {\rm(J. Franklin)}. {\sl The
$[0,1)$ sequence $U↓0$, $U↓1$, $\ldotss$, with}
$$U$↓n = (\theta ↑n$ mod 1)\eqno (26)
|qctr \9skip $is $∞$-distributed for almost all real numbers \theta
> 1. That is, the set$
$$\{\theta | \theta > 1 and (26) is not $∞$-distributed\}
|qctr \9skip {\sl is of measure zero.}

|qleft \12skip \quad The proofs of this theorem and some generalizations
are given in Franklin's paper quoted below.

|qleft \12skip \quad Franklin has shown that $\theta$ must be
a transcendental number for (26) to be $∞$-distributed. The powers
($π↑n$ mod 1) have been laboriously computed for $n ≤ 10000$,
using multiple-precision arithmetic, and the most significant
35 bits of each of these numbers, stored on a disk file, have
been sucessfully used as a source of uniform deviates. We have
the interesting situation that, by Theorem F, the probability
that the powers $(π↑n$ mod 1) are $∞$-distributed is equal to
1; yet because there are uncountably many real numbers, this
gives us no information as to whether the sequence is really
$∞$-distributed or not. It is a fairly safe bet that nobody in
our lifetimes will ever {\sl prove} that this particular sequence
is {\sl not} $∞$-distributed; but it might not be. Because of
these considerations, one may legitimately wonder if there is
any {\sl explicit} sequence which is $∞$-distributed; i.e., {\sl
is there an algorithm to compute real numbers U↓n for all n
≥ 0, such that the sequence \langle U↓n\rangle is $∞$-distributed?}
The answer is yes, as shown for example by D. E. Knuth in {\sl
BIT \bf 5} (1965), 246--250. The sequence constructed there
consists entirely of rational numbers; in fact, each number
$U↓n$ has a terminating representation in the binary number
system. Another construction of an explicit $∞$-distributed sequence,
somewhat more complicated than the sequence just cited, follows
from Theorem W below. See also N. M. Korobov, {\sl Izv.\ Akad.\
Nauk SSSR \bf 20} (1956), 649--660.

\yyskip\noindent{\bf C. Does $∞$-distributed $=$ random?}\xskip
In view of all the above theory about $∞$-distributed
sequences, we can be sure of one thing: the concept of an $∞$-distributed
sequence is an important one in mathematics. There is also a
good deal of evidence that the following statement is a valid
formulation of the intuitive idea of randomness:

\thbegin Definition R1. {\sl A $[0,1)$ sequence is defined to
be ``random'' if it is an $∞$-distributed sequence$.

|qleft \12skip We have seen that sequences meeting this definition
will satisfy all the statistical tests of Section 3.3.2 and
many more.

Let us attempt to criticize this definition objectively. First
of all, is every ``truly random'' sequence $∞$-distributed? There
are uncountably many sequences $U↓0, U↓1, . . $. of real numbers
between zero and one. If a truly random number generator is
sampled to give values $U↓0$, $U↓1$, $\ldotss $, any of the possible
sequences may be considered equally likely, and some of the
sequences (indeed, uncountably many of them) are not even equi??distributed.
On the other hand, using any reasonable definition of probability
on this space of all possible sequences leads us to conclude
that a random sequence is $∞$-distributed {\sl with probability
one.} We are therefore led to formalize Franklin's definition
of randomness (as given at the beginning of this section) in
the following way:

\thbegin Definition R2. {\sl A $[0,1)$ sequence $\langle U↓n\rangle$
is defined to be ``random'' if, whenever P is a property such
that P(\langle V↓n\rangle ) holds with probability one for a
sequence \langle V↓n\rangle of independent samples of random
variables from the uniform distribution, then P(\langle U↓n\rangle
) is true$.

Is it perhaps possible that Definition R1 is equivalent to Definition
R2? Let us try out some possible objections to Definition R1,
and see whether these cricicisms are valid.

In the first place, Definition R1 deals only with limiting properties
of the sequence as $n → ∞$. There are $∞$-distributed sequences
in which the first million elements are all zero; should such
a sequence be considered random?

This objection is not very valid. If $e$ is any positive number,
there is no reason why the first million elements of a sequence
should not all be less than $\epsilon $; as pointed out earlier
in this section, there is no legitimate way to say if a finite
sequence is random or not. With probability one, a truly random
sequence contains infinitely many runs of a million consecutive
elements less than $\epsilon $, so why can't this happen at
the beginning of the sequence?

On the othe|newtype W58320---Computer Programming\quad (Knuth/
%folio 204 galley 4 (C) Addison-Wesley 1978	-
Addison-Wesley)\quad f. 204\quad ch. 3\quad g. 4d
$$\quad Now let $P$ be the property that $no$ element of the
sequence is equal to zero; again, $P$ is true with probability
one, so by Definition R2 any sequence with a zero rlrment is
not random. More generally, however, let $X↓0$ be any fixed
number between zero and one, and let $P$ be the property that
no element of the sequence is equal to $x↓0$; Definition R2
now says that no random sequence may contain the element $x↓0$!
We can now prove that {\sl no sequence satisfies the condition
of Definition R2. (}For if $U↓0, U↓1, . . $. is such a sequence,
take $x↓0 = U↓0.)$

Therefore if R1 is too weak a definition, R2 is certainly too
strong. The ``right'' definition must be less strict than R2.
We have not really shown that R1 is too weak, however, so let
us continue to attack it some more. As mentioned above, an $∞$-distributed
sequence of {\sl rational} numbers has been constructed. (Indeed,
this is not so surprising: see exercise 18.) Almost all real
numbers are irrational; perhaps we should insist that
$$Pr($U↓n$ is rational) = 0
|qctr \9skip for a random sequence.

Note that the definition of equidistribution says that Pr($u
≤ U↓n < v) = v - u$. There is an obvious way to generalize this
definition, using measure theory: ::If $S \subset $[0,1)$$ is
a set of measure $\mu $, then
$$Pr($U↓n ε S) = \mu ,\eqno (27)$
|qctr \9skip for all random sequences $\langle U↓n\rangle .$''
In particular, if $S$ is the set of rationals, it has measure
zero, so no sequence of rational numbers is equi??distributed
in this generalized sense. It is reasonable to expect that Theorem
B could be extended to Lebesgue integration instead of Riemann
integration, if property (27) is stipulated. However, once again
we find that definition (27) is too strict, for $no$ sequence
satisfies that property. If $U↓0, U↓1, . . $. is any sequence,
the set $S = \{U↓0, U↓1, . . .\}$ is of measure zero, yet Pr($U↓n
ε S) = 1$. Thus, by the force of the same argument we used to
exclude rationals from random sequences, we can exclude all
random sequences.

So far Definition R1 has proved to be defensible. There are,
however, some quite valid objections to it. For example, if
we have a random sequence in the intuitive sense, the infinite
subsequence
$$$U↓0, U↓1, U↓4, U↓9, U↓n|supinf 2, . . .\eqno (28)$
|qctr \9skip should also be a random sequence. This is not always
true for an $∞$-distributed sequence. (In fact, if we take any
$∞$-distributed sequence and set $U↓n|supinf 2 ← 0$ for all $n$,
the counts $\nu ↓k(n)$ which appear in the test of $k$-distributivity
are changed by at most \sqrt{$n}$, so the limits of the ratios
$\nu ↓k(n)/n$ remain unchanged.) Therefore R1 definitely fails
to satisfy this randomness criterion.

Perhaps we should strengthen R1 as follows:

\thbegin Definition R3. {\sl A $[0,1)$ sequence is said to be
``random'' if each of its infinite subsequences is $∞$-distributed.}

|qleft \12skip But once again we find this definition is too
strict. If $\langle U↓n\rangle$ is any equi??distributed sequence,
it has a monotonic subsequence with $U↓s|infinf 0 < U↓s|infinf
1 < U↓s|infinf 2 < \cdotss$.

The secret is to restrict the subsequences so that they could
be defined by a man who does not look at $U↓n$ before he decides
whether or not it is to be in the subsequence. The following
definition now suggests itself:

\thbegin Definition R4. {\sl A $[0,1)$ sequence $\langle
U↓n\rangle$ is said to be ``random'' if, for every effective
algorithm which specifies an infinite sequence of distinct nonnegative
integers s↓n for n ≥ 0, the subsequence U↓s|infinf 0, U↓s|infinf
1, . . . corresponding to this algorithm is $∞$-distributed$.

|qleft \12skip \quad The algorithms referred to in this definition
are effective procedures which compute $s↓n$, given $n$. (See
Section 1.1.) Thus, for example, the sequence $\langle π↑n$
mod 1\rangle will {\sl not} satisfy R4, since it is either not
equidistributed or there is an effective algorithm which determines
an infinite subsequence $s↓n$ with $(π↑s|infsup 0$ mod 1) <
($π↑s|infsup 1$ mod 1) < \cdotss$. Similarly, {\sl no explicitly
defined sequence can satisfy Definition R{\sl 4; }}this is appropriate,
if we agree that no explicitly defined sequence can really be
random. It is quite likely, however, that the sequence $(\theta
↑n$ mod 1\rangle will satisfy Definition R4, for almost all
real numbers $\theta > 1$; this is no contradiction, since almost
all $\theta$ are uncomputable by algorithms. The following facts
are known, for example: (i) The sequence $\langle \theta ↑n$
mod 1\rangle satisfies Definition R4 for almost all real $\theta
> 1$, if ``$∞$-distributed'' is replaced by ``1-distributed.''
This theorem was proved by J. F. Koksma, {\sl Compositio Mathematica}
{\bf 2} (1935), 250--258. (ii) The particular sequence \langle
$\theta ↑{s(n)}$ mod 1\rangle is $∞$-distributed for almost all
real $\theta > 1$, if $\langle s(n)\rangle$ is a sequence of
integers for which $s(n + 1) - s(n) → ∞$ as $n → ∞$. For example,
we could have $s(n) = n↑2$, or $s(n) = \lfloor n$ log $n3$.

Definition R4 is much stronger than Definition R1; but it is
still reasonable to claim that Definition R4 is too weak. For
example, let $\langle U↓n\rangle$ be a truly random sequence,
and define the subsequence $\langle U↓s|infinf n\rangle$ by
the following rules: $s↓0 = 0$, and (for $n > O) s↓n$ is the
smallest integer ≥$n$ for which $U↓s|infinf n↓{-1}, U↓s|infinf
n↓{-2}, \ldotss , U↓s|infinf n↓{-n}$ are all less than ${1\over
2}$. Thus we are considering the subsequence of values following
the first consecutive run of $n$ values less than ${1\over 2}$.
Suppose that ``$U↓n < {1\over 2}$'' corresponds to the value
``heads'' in the flipping of a coin. Gamblers tend to feel that
a long run of ``heads'' makes the opposite condition, ``tails,''
more probable, assuming a true coin is being used; and the subsequence
$\langle U↓s|infinf n\rangle$ just defined corresponds to a
gambling system for a man who places his $n$th bet on the coin
toss following the first run of $n$ consecutive ``heads.'' The
gambler may think that Pr($U↓s|infinf n ≥ {1\over 2})$ is more
than ${1\over 2}$, but of course in a truly random sequence,
$\langle U↓s|infinf n\rangle$ will be completely random. No
gambling system will ever able to beat the odds! Definition
R4 says nothing about subsequences formed according to such
a gambling system, and so apparently we need something more.

Let us define a ``subsequence rule'' ??R as an infinite sequence
of functions $\langle f↓n(x↓1, \ldotss , x↓n)\rangle$ where,
for $n ≥ 0, f↓n$ is a function of $n$ variables, and the value
of $f↓n(x↓1, \ldotss , x↓n)$ is either 0 or 1. Here $x↓1, \ldotss
, x↓n$ are elements of some set $S$. (Thus, in particular, $f↓0$
is a constant function, either 0 or 1.) A subsequence rule ??R
defines a subsequence of any infinite sequence $\langle X↓n\rangle$
of elements of $S$ as follows: {\sl The n}th {\sl term X↓n is
in the subsequence \langle X↓n\rangle ??R if and only if f↓n(X↓0,
X↓1, \ldotss , X↓{n-1}) = 1.} Note that the subsequence $\langle
X↓n\rangle ??R$ thus defined is not necessarily infinite, and
it may in fact be the null subsequence.

The ``gambler's subsequence'' which was described above corresponds
to the following subsequence rule: ``$f↓0 = 1$; and for $n >
0, f↓n(x↓1, \ldotss , x↓n) = 1$ if and only if there is some
$k, 0 < k ≤ n$, such that $x↓m < {1\over 2}, x↓{m-1} < {1\over
2}, \ldotss , x↓{m-k+1} < {1\over 2}$, when $m = n$ but not when
$k ≤ m < n.$''

A subsequence rule ??R is said to be {\sl computable} if there
is an effective algorithm which determines the value of $f↓n(x↓1,
\ldotss , x↓n)$, when $n, x↓1, \ldotss , x↓n$ are given as input.
In a definition of randomness, we should restrict ourselves
to computable subsequence rules, or else we obtain a definition
like R3 above, which is too strong. Effective algorithms cannot
deal nicely with arbitrary real numbers as inputs; for example,
if a real number $x$ is specified by an infinite radix-10 expansion,
there is no algorithm to determine if $x$ is <${1\over 3}$ or
not, since all digits of the number 0.333 . . . would have to
be examined. Therefore computable subsequence rules do not apply
to all $[0,1)$ sequences, and it is convenient to base our next
definition on $b$-ary sequences:

\thbegin Definition R5. {\sl A $b$-ary sequence is said to be
``random'' if every infinite subsequence defined by a computable
subsequence rule is $1$-distributed.}

A $[0,1)$ sequence \langle U$↓n\rangle is said to be ``random''
if the b-ary sequence \langle \lfloor bU↓n\rfloor \rangle is
``random'' for all integers b ≥ 2$.
|qleft u|newtype W58320---Comp
%folio 206 galley 5 (C) Addison-Wesley 1978	-
uter Programming\quad (Knuth/Addison-Wesley)\quad f. 206\quad
ch. 3\quad g. 5d
\yyskip Note that Definition R5 says only ``1-distributed,''
not ``$∞$-distributed.'' It is interesting to verify that this may
be done without loss of generality. For we may define an obviously
computable subsequence rule ??R($a↓1 \ldotsm a↓k)$ as follows,
given any $b$-ary number $a↓1 \ldotsm a↓k:$ Let $f↓n(x↓1, \ldotss
, x↓n) = 1$ if and only if $n ≥ k - 1$ and $x↓{n-k+1} = a↓1$,
$\ldotss$, $x↓{n-1} = a↓{k-1}$, $x↓n = a↓k$. Now if $\langle X↓n\rangle$
is a $k$-distributed $b$-ary sequence, this rule ??R($a↓1 \ldotsm
a↓k)--$-which selects the subsequence consisting of those terms
just following an occurrence of $a↓1 \ldotsm a↓k--$-defines an
infinite subsequence; and if this subsequence is 1-distributed,
each of the $(k + 1)$-tuples $a↓1 \ldotsm a↓ka↓{k+1}$ for 0 ≤
$a↓{k+1} < b$ occurs with probability $1/b↑{k+1}$ in \langle
$X↓n\rangle $. Thus we can prove that a sequence satisfying
Definition R5 is $k$-distributed for all $k$, by induction on
$k$. Similarly, by considering the ``composition'' of subsequence
rules---if ??R$↓1 defines an infinite subsequence \langle X↓n\rangle
??R↓1$, then we can define ??R$↓1??R↓2 to be the subsequence
rule for which \langle X↓n\rangle ??R↓1??R↓2 = (\langle X↓n\rangle
??R↓1)??R↓2--$-we find that all subsequences considered in Definition
R5 are $∞$-distributed. (See exercise 32.)

The fact that $∞$-distribution comes out of Definition R5 as a
very special case is encouraging, and it is a good indication
that we may at last have found the definition of randomness
which we have been seeking. But alas, there still is a problem.
It is not clear that sequences satisfying Definition R5 must
satisfy Definition 4. The ``computable subsequence rules'' we
have just specified always enumerate subsequences $\langle X↓s|infinf
n\rangle$ for which $s↓0 < s↓1 < \cdotss$, but $\langle s↓n\rangle$
does not have to be monotone in R4; it must only satisfy the
condition $s↓n ≠ s↓m$ for $n ≠ m$.

To meet this objection, we may combine Definitions R4 and R5
as follows:

\thbegin Definition R6. {\sl A $b$-ary sequence $\langle X↓n\rangle$
is said to be ``random'' if, for every effective algorithm which
specifies an infinite sequence of distinct nonnegative integers
\langle s↓n\rangle as a function of n and the values of X↓s|infinf
0, \ldotss , X↓s|infinf n|infinf -|infinf 1, the subsequence
\langle X↓s|infinf n\rangle corresponding to this algorithm
is ``random'' in the sense of Definition R{\sl 5}$.

A $[0,1)$ sequence \langle U$↓n\rangle is said to be ``random''
if the b-ary sequence \langle \lfloor bU↓n\rfloor \rangle is
``random'' for all integers b ≥ 2$.

|qleft \12skip \quad The author contends?? that this definition
surely meets all reasonable philosophical requirements for randomness,
and so it provides an answer to the principal question posed
in this section.

|qleft \2skip ------------------
|qleft |newtype \quad ?? At least, he felt that way when originally
preparing the material for this section.

\subsectionbegin{D. Existence of random sequences}
We have seen that Definition R3 is too strong, in the sense
that no sequences could exist satisfying that definition; and
the formulation of Definitions R4, R5, and R6 above was carried
out in an attempt to recapture the essential characteristics
of Definition R3. In order to show that Definition R6 is not
overly restrictive, it is still necessary for us to prove that
sequences satisfying all these conditions exist. Intuitively,
we feel quite sure that such sequences exist, because we believe
that a truly random sequence exists and satisfies Definition
R6; but a proof is really necessary to show that the definition
is consistent.

An interesting method for constructing sequences satisfying
Definition R5 has been given by A. Wald. The construction starts
with a very simple 1-distributed sequence:

\thbegin Lemma T. {\sl Let the sequence of real numbers
$\langle V↓n\rangle$ be defined in terms of the binary system
as follows:
|qleft V$↓0 |tab = 0,\qquad V↓1 = .1,\qquad V↓2 = .01,\qquad
V↓3 = .11,\qquad V↓4 = .001,\qquad . . .⊗\4skip \hfill V↓n ⊗=
.c↓r \ldotsm c↓11\qquad$ if\qquad $n = 2↑r + c↓12↑{r-1} + \cdots
+ c↓r.\eqno (29)\cr
\9skip Let I↓b|infinf 1↓{...}b|infinf r denote the set of all
real numbers in $[0,1)$ whose binary representation begins with
0.b↓1 \ldotsm b↓r{\sl ;} thus$
$$I↓{b$↓1...b↓r} = [0.b↓1 \ldotsm b↓r, o.b↓1 \ldotsm b↓r + 2↑{-r}).\eqno
(30)$
|qctr \9skip Then if \nu (n) denotes the number of V$↓k in I↓b|infinf
1↓{...b}|infinf r for 0 ≤ k < n, we have$
$$|\nu (n)/n - 2$↑{-r}| ≤ 1/n.\eqno (31)$
|qctr \9skip Proof. \xskip Since $\nu (n)$ is the number of
$k$ for which $k$ mod $2↑r = b↓r \ldotsm b↓1$, we have $\nu (n)
= t$ or $t + 1$ when \lfloor $n/2↑r\rfloor = t$. Hence |$\nu
(n) - n/2↑r| ≤ 1$.

|qleft \12skip \quad It follows from (31) that the sequence
\langle \lfloor $2↑rV↓n\rfloor \rangle$ is an equidistributed
2$↑r$-ary sequence; hence by Theorem A, $\langle V↓n\rangle$
is an equidistributed $[0,1)$ sequence. Indeed, it is pretty
clear that $\langle V↓n\rangle$ is about as equidistributed
as a $[0,1)$ sequence can be. (For further discussion of this
and related sequences, see J. C. van der Corput, {\sl Proc.\
Koninklijke Nederl.\ Akad.\ Wetenschappen \bf 38} (1935),
813--821, 1058--1066; J. H. Halton, {\sl Numerische Math.\
\bf 2} (1960), 84--90, 196; L. H. Ramshaw, to appear.)

Now let ??R$↓1, ??R↓2, . . . be infinitely many subsequence
rules; we would like to find a sequence \langle U↓n\rangle$
for which all the infinite subsequences $\langle U↓n\rangle
??R↓j$ are equidistributed.

\algbegin Algorithm W (Wald sequence).
Given an infinite set of subsequence rules ??R$↓1, ??R↓2, $\ldotss$,
which define subsequences of $[0,1)$ sequences of rational
numbers, this procedure defines a $[0,1)$ sequence $\langle U↓n\rangle
$. The computation involves infinitely many auxiliary variables
$C[a↓1, \ldotss , a↓r]$ where $r ≥ 1$ and where $a↓j = 0$ or
1 for 1 ≤ $j ≤ r$. These variables are initially all zero.

\algstep W1. [Initialize {\sl n.]} Set $n ← 0$.

\algstep W2. [Initialize {\sl r.]} Set $r ← 1$.

\algstep W3. [Test ??R$↓r.]$ If the element $U↓n$ is to be in
the subsequence defined by ??R$↓r$, based on the values of $U↓k$
for 0 ≤ $k < n$, set $a↓r ← 1$; otherwise set $a↓r ← 0$.

\algstep W4. [$B[a↓1, \ldotss , a↓r]$ full?] If $C[a↓1, \ldotss
, a↓r] < 3 \cdot 4↑{r-1}$, go to W6.

\algstep W5. [Increase {\sl r.]} Set $r ← r + 1$ and return
to W3.

\algstep W6. [Set $U↓n.]$ Increase $C[a↓1, \ldotss , a↓r]$ by
1 and let $k$ be the new value of $C[a↓1, \ldotss , a↓r]$. Set
$U↓n ← V↓k$, where $V↓k$ is defined in Lemma T above.

\algstep W7. [Advance {\sl n.]} Increase $n$ by 1 and return
to W2.

|qleft \3skip \9skip \quad Strictly speaking, this is not an
algorithm, since it doesn't terminate; it would of course be
easy to modify the procedure to stop when $n$ reaches a given
value. The reader will find it easier to grasp the idea of the
construction if he tries it by hand, replacing the number 3
\cdot 4$↑{r-1}$ of step W4 by 2$↑r$ during this experiment.

Algorithm W is not meant to be a practical source of random
numbers; it is intended to serve only a theoretical purpose:

\thbegin Theorem W. {\sl Let $\langle U↓n\rangle$ be the sequence of rational
numbers defined by Algorithm W, and let $k$ be a positive integer.
If the subsequence $\langle U↓n\rangle ??R↓k is infinite, it
is $1$-distributed.}

|qleft \12skip Proof. \xskip Let $A[a↓1, \ldotss , a↓r]$ denote
the (possibly empty) subsequence of $\langle U↓n\rangle$ containing
precisely those elements $U↓n$ which, for all $j, 1 ≤ j ≤ r$,
belong to subsequence $\langle U↓n\rangle ??R↓j$ if $a↓j = 1$
and do not belong to subsequence $\langle U↓n\rangle ??R↓j$
if $a↓j = 0$.

It suffices to prove, for all $r ≥ 1$ and all pairs of binary
numbers $a↓1 \ldotsm a↓r$ and $b↓1 \ldotsm b↓r$, that Pr($U↓n
ε I↓b|infinf 1↓{...b}|infinf r)≥ = 2↑{-r}$ with respect to the
subsequence $A[a↓1, \ldotss , a↓r]$, whenever the latter is infinite.
[See Eq.\ (30).] For if $r ≥ k$, the infinite sequence \langle
$U↓n\rangle ??R↓k$ is the finite union of the disjoint subsequences
$A[a↓1, \ldotss , a↓r]$ for $a↓k = 1$ and $a↓j = 0$ or 1 for
1 ≤ $j ≤ r, j ≠ k$; and it follows that Pr($U↓n ε I↓b|infinf
1↓{...b}|infinf r) = 2↑{-r}$ with respect to $\langle U↓n\rangle
??R↓k$. (See exercise 33.) This is enough to show that the sequence
is 1-distributed, by Theorem A.
|qleft u|newtype W58320---
%folio 209 galley 6 (C) Addison-Wesley 1978	-
Computer Programming\quad (Knuth/Addison-Wesley)\quad f. 209\quad
ch. 3\quad g. 6d
Let $B[a↓1, \ldotss , a↓r]$ denote the subsequence of
$\langle U↓n\rangle$ which consists of the values for those
$n$ in which $C[a↓1, \ldotss , a↓r]$ is increased by one in step
W6 of the algorithm. By the algorithm, $B[a↓1, \ldotss , a↓r]$
is a finite sequence with at most $3 \cdot 4↑{r-1}$ elements.
All but a finite number of the members of $A[a↓1, \ldotss , a↓r]$
come from the subsequences $B[a↓1, \ldotss , a↓r, \ldotss , a↓t]$,
where $a↓j = 0$ or 1 for $r < j ≤ t$.

Now assume that $A[a↓1, \ldotss , a↓r]$ is infinite, and let
$A[a↓1, \ldotss , a↓r] = \langle U↓{s↓n}\rangle$ where $s↓0
< s↓1 < s↓2 ≤ \cdotss$. If $N$ is a large integer, with $4↑r
≤ 4↑q < N ≤ 4↑{q+1}$, it follows that the number of values of
$k < N$ for which $U↓{s↓k}$ is in $I↓{b↓1\ldotsm b↓r}$
is (except for finitely many elements at the beginning of
the subsequence)
$$\nu (N) = \nu (N↓1) + \cdots + \nu (N↓m).$$
Here $m$ is the number of subsequences $B[a↓1,
\ldotss , a↓t]$ listed above in which $U↓{s↓k}$ appears
for some $k < N$; $N↓j$ is the number of values of $k$ with $U↓{s↓k}$
in the corresponding subsequence; and $\nu (N↓j)$ is the
number of such values which are also in $I↓{b↓1\ldotsm b↓r}$.
Therefore by Lemma T,
$$\eqalign{|\nu (N) - 2↑{-r}N| ⊗ = |\nu (N↓1) - 2↑{-r}N↓1 + \cdots
+ \nu (N↓m) - 2↑{-r}N↓m| \cr\noalign{\vskip 3pt}
⊗≤ |\nu (N↓1) - 2↑{-r}N↓1|
+ \cdots + |\nu (N↓m) - 2↑{-r}N↓m|\cr\noalign{\vskip 3pt}
⊗≤ m ≤ 1 + 2 + 4 + \cdots + 2↑{q-r+1} < 2↑{q+1}.\cr}$$
The inequality on $m$ follows here from the fact that,
by our choice of $N$, $U↓{s↓N}$ is in $B[a↓1, \ldotss , a↓t]$
for some $t ≤ q + 1$.

Therefore
$$|\nu (N)/N - 2↑{-r}| ≤ 2↑{q+1}/N < 2/\sqrt{N}.\quad\blackslug$$

\yyskip To show finally that sequences satisfying
Definition R5 exist, we note first that if $\langle U↓n\rangle$
is a $[0,1)$ sequence of rational numbers and if ??R is a computable
subsequence rule for a $b$-ary sequence, we can make ??R into
a computable subsequence rule rule ??R↑\prime for $??U↓n\approx$
by letting $f↑{↑\prime}↓{n}(x↓1, \ldotss , x↓n)$ in ??R↑\prime
equal $f↓n(\lfloor bx↓1\rfloor , \ldotss , \lfloor bx↓n\rfloor
)$ in ??R. If the sequence $\langle U↓n\rangle ??R↑\prime$ is
equidistributed, so is the sequence \langle \lfloor $bU↓n\rfloor
\rangle ??R$. Now the set of all computable subsequence rules
for $b$-ary sequences, for all values of $b$, is countable (since
only countably many effective algorithms are possible), so they
may be listed in some sequence ??R$↓1, ??R↓2$, $\ldotss$; therefore
Algorithm W defines a $[0,1)$ sequence which is random in the
sense of Definition R5$.

This brings us to a somewhat paradoxical situation. As we mentioned
earlier, no effective algorithm can define a sequence which
satisfies Definition R4, and for the same reason there is no
effective algorithm which defines a sequence satisfying Definition
R5. A proof of the existence of such random sequences is necessarily
nonconstructive; how then can Algorithm W construct such a sequence?

There is no contradiction here; we have merely stumbled on the
fact that the set of all effective algorithms cannot be enumerated
by an effective algorithm. In other words, there is no effective
algorithm to select the $j$th computable subsequence rule $??R↓j$;
this happens because there is no effective algorithm to determine
if a computational method ever terminates. (We shall return
to this topic in Chapter 11.) Important large classes of algorithms
{\sl can} be systematically enumerated; thus, for example, Algorithm
W shows that is possible to construct, with an effective algorithm,
a sequence which satisfies Definition R5 if we restrict consideration
to subsequence rules which are ``primitive recursive.''

By modifying step W6 of Algorithm W, so that it sets $U↓n ←
V↓{k+t}$ instead of $V↓k$, where $t$ is any nonnegative integer
depending on $a↓1$, $\ldotss$, $a↓r$, we can show that are {\sl
uncountably} many $[0,1)$ sequences satisfying Definition R5.

The following theorem shows still another way to prove the existence
of uncountably many random sequences, using a less direct argument
based on measure theory, even if the strong definition R6 is
used:

\thbegin Theorem M. {\sl Let the real number $x$, $0 ≤ x
< 1$, correspond to the binary sequence $\langle X↓n\rangle$ if
the binary representation of $x$ is $(0.X↓0X↓1 \ldotsm)↓2$. Under this
correspondence, almost all $x$ correspond to binary sequences
which are random in the sense of Definition R6.} (In other
words, the set of all real $x$ which correspond to a binary
sequence which is nonrandom by Definition R6 has measure zero.)

|qleft \12skip {\sl Proof. \xskip} Let ??S be an effective algorithm
which determines an infinite sequence of distinct nonnegative
integers $\langle s↓n\rangle $, where the choice of $s↓n$ depends
only on $n$ and $X↓s|infinf k$ for 0 ≤ $k < n$; and let ??R
be a computable subsequence rule. Then any binary sequence $\langle
X↓n\rangle$ leads to a subsequence $\langle X↓s|infinf n\rangle
??R$, and Definition R6 says this subsequence must either be
finite or 1-distributed. It suffices to prove that {\sl for
fixed ??R and ??S the set N(??r, ??S) of all real x corresponding
to \langle X↓n\rangle , such that \langle X↓s|infinf n\rangle
??R is infinite and not {\sl 1}-distributed, has measure zero.}
For $x$ has a nonrandom binary representation if and only if
$x$ is in \mathop{∪} $N(??R, ??S)$, taken over the countably
many choices of ??R and ??S.

Therefore let ??R and ??S be fixed. Consider the set $T(a↓1a↓2
\ldotsm a↓r)$ defined for all binary numbers $a↓1a↓2 \ldotsm a↓r$
as the set of all $x$ corresponding to $\langle X↓n\rangle $,
such that $\langle X↓s|infinf n\rangle ??9$ has $≥r$ elements
whose first $r$ elements are respectively equal to $a↓1, a↓2,
\ldotss , a↓r$. Our first result is that
$$$T(a↓1a↓2 \ldotsm a↓r)\qquad$ has measure\qquad $≤2↑{-r}.\eqno
(32)$
|qctr \9skip To prove this, we start by observing that $T(a↓1a↓2
\ldotsm a↓r)$ is a measurable set: Each element of $T(a↓1a↓2
\ldotsm a↓r)$ is a real number $x = (0.X↓0X↓1 \ldotsm)↓2$ for which
there exists an integer $m$ such that algorithm ??S determines
distinct values $s↓0$, $s↓1$, $\ldotss$, $s↓m$, and rule ??R determines
a subsequence of $X↓s|infinf 0$, $X↓s|infinf 1$, $\ldotss$, $X↓s|infinf
m$ such that $X↓s|infinf m$ is the $r$th element of this sequence.
The set of all real $y = 0.Y↓0Y↓1 . . $. such that $Y↓s|infinf
k$ for 0 ≤ $k ≤ m$ also belongs to $T(a↓1a↓2 \ldotsm a↓r)$, and
this is a measurable set consisting of the finite union of dyadic
subintervals $I↓b|infinf 1↓{...}|infinf t$. Since there are
only countably many such dyadic intervals, we see that $T(a↓1a↓2
\ldotsm a↓r)$ is a countable union of dyadic intervals, and it
is therefore measurable. Furthermore, this argument can be extended
to show that the measure of $T(a↓1 \ldotsm a↓{r-1}0)$ equals
the measure of $T(a↓1 \ldotsm a↓{r-1}1)$, since the latter is
a union of dyadic intervals obtained from the former by requiring
that $Y↓s|infinf k = X↓s|infinf k$ for $0 ≤ k < m$ and $Y↓s|infinf
m ≠ X↓s|infinf m$. Now since
$$$T(a↓1 \ldotsm a↓{r-1}0) ∪ T(a↓1 \ldotsm a↓{r-1}1) \subset T(a↓1
\ldotsm a↓{r-1})$,
|qctr \9skip the measure of $T(a↓1a↓2 \ldotsm a↓r)$ is at most
one-half the measure of $T(a↓1 \ldotsm a↓{r-1})$. The inequality
(32) follows by induction on $r$.

Now that (32) has been established, the remainder of the proof
is essentially to show that the binary representations of almost
all real numbers are equi??distributed. The next few paragraphs
constitute a rather ling but not difficult proof of this fact,
and they serve to illustrate typical estimation techniques in
mathematical|newtype W58320---Computer
%folio 212 galley 7 (C) Addison-Wesley 1978	-
For $0 < \epsilon < 1$, let $B(r, \epsilon )$ be $\union
T(a↓1 \ldotsm a↓r)$, where the union is taken over all binary
numbers $a↓1 \ldotsm a↓r$ for which the number $\nu (r)$ of zeros
among $a↓1 \ldotsm a↓r$ satisfies
$$|\nu (r) - {1\over 2}r| ≥ 1 + \epsilon r.$$
The number of such binary numbers is $C(r, \epsilon
) = \sum {r\choose k}$ summed over the values of $k$ with $|k
- {1\over 2}r| ≥ 1 + \epsilon r$. A suitable estimate for the
tail of the binomial distribution can be obtained by the following
standard trick: Let $x$ be any positive number less than 1,
and let $s = ({1\over 2} + \epsilon )r$. Then
$$\sum ↓{k≥s}{r\choose k} ≤ \sum ↓{k≥s}{r\choose k}x↑{s-k}
≤ \sum ↓{k≥0}{r\choose k}x↑{s-k} = x↑s\left(1 + {1\over
x}\right)↑r.$$
By elementary calculus, the minimum value of $x↑s(1
+ 1/x)↑r$ occurs when $x = r/s - 1 = (1 - 2\epsilon )/(1 + 2\epsilon
)$, and this value of $x$ yields
$$\sum ↓{k≥({1\over2}+\epsilon )r}{r\choose k} ≤ \left({2\over
(1 + 2\epsilon )↑{{1\over2}+\epsilon}(1 - 2\epsilon )↑{{1\over2}-\epsilon}\right)↑r.r$.
$$ Now when $\epsilon < {1\over 2}$ we have
$$$({1\over 2} + \epsilon )$ln(1 + $2\epsilon ) + ({1\over 2}
- \epsilon )$ln(1 - 2$\epsilon ) = {1\over 1 \cdot 2} (2\epsilon
)↑2 + {1\over 3 \cdot 4} (2\epsilon )↑4 + {1\over 5 \cdot 6}
(2\epsilon )↑6 + \cdots > 2\epsilon ↑2$,
|qctr \9skip hence the denominator in our estimate is larger
than $e↑{-2|}≤e|supsup 2$. We have proved that
$$$\sum ↓{k≥(1/2+\epsilon )r}\left({r\atop k}} < 2↑re↑{-2|}≤e|supsup
2r,\qquad$ for all\qquad $r > 0\qquad$ and\qquad 0 < $\epsilon
< {1\over 2}.\eqno (33)$
|qctr \9skip But $C(r, \epsilon )$ is twice this left-hand quantity,
hence by (32) and (33)

|qleft \9skip $B(r, \epsilon )\qquad$ has measure\qquad $≤2↑{-r}C(r,
\epsilon ) < 2e↑{-2|}≤e|supsup 2↑r$.
|qctr \9skip \quad The next step is to define
$$$B↑\prime (r, \epsilon ) = B(r, \epsilon ) ∪ B(r + 1, \epsilon
) ∪ B(r + 2, \epsilon ) ∪ \cdotss$.
|qctr \9skip The measure of $B↑\prime (r, \epsilon )$ is at
most $\sum ↓{k|}¬R↓r ke↑{-|}≤e|supsup 2↑k$, and this is the
remainder of a convergent series so
$$\mathop{lim↓{|raise2 $r→∞}$ (measure of $B↑\prime (r, \epsilon
)\bigrp = 0.\eqno (34)$
|qctr \9skip \quad Now if $x$ is a real number whose binary
expansion $0.X↓0X↓1 . . $. leads to an infinite sequence $\langle
X↓s|infinf n\rangle ??R$ that is not 1-distributed, and if $\nu
(r)$ denotes the number of zeros in the first $r$ elements of
the latter sequence, then
$$$|\nu (r)/r - {1\over 2}|bigcard ≥ 2\epsilon $,
|qctr \9skip for some $\epsilon > 0$ and infinitely many $r$.
This means $x$ is in $B↑\prime (r, \epsilon )$ for all $r$.
So finally we find that
$$$N(??R, ??S) = \mathop{\mathop{∪}↓{t≥2} \mathop{\mathop{∩}??r≥1??
B↑\prime (r, 1/t)$,
|qctr \9skip and, by (34), \mathop{∩}$↓|εr↓|¬R↓1 B↑\prime (r,
1/t)$ has measure zero for all $t$. Hence $N(??R, ??S)$ has
measure zero.

|qleft \12skip \quad From the existence of {\sl binary} sequences
satisfying Definition R6, we can show the existence if $[0,1)$
sequences which are random in this sense. For details, see exercise
36. The consistency of Definition R6 is thereby established.

\subsectionbegin{E. Random finite sequences} An argument
was given above to indicate that it is impossible to define
the concept of randomness for finite sequences; any given finite
sequence is as likely as any other. Still, nearly everyone would
agree that the sequence 011101001 is ``more random'' than 101010101,
and even the latter sequence is ``more random'' than 000000000.
Although it is true that truly random sequences will exhibit
locally nonrandom behavior, we would expect such behavior only
in a long finite sequence, not in a short one.

Several ways for defining the randomness of a finite sequence
have been proposed, and only a few of the ideas will be sketched
here. Let us consider only the case of $b$-ary sequences.

Given a $b$-ary sequence $X↓1$, $X↓2$, $\ldotss$, $X↓N$, we can say
that
$$Pr\biglp $S(n)\bigrp \approx p,\qquad$ if\qquad $|\nu (N)/N
- p| ≤ 1/\sqrt{N}$,
|qctr \9skip where $\nu (n)$ is the quantity appearing in Definition
A at the beginning of this section. The above sequence can be
called ``$k$-distributed'' if
$$Pr($X↓nX↓{n+1} \ldotsm X↓{n+k-1} = x↓1x↓2 \ldotsm x↓k) \approx
1/b↑$
k|qctr \9skip for all $b$-ary numbers $x↓1x↓2 \ldotsm x↓k$. (Cf.\
Definition D; unfortunately a sequence may be $k$-distributed
by this new definition when it is not $(k - 1)$-distributed.)
|qleft
%folio 214 galley 8 (C) Addison-Wesley 1978	-
A definition of randomness may now be given analogous
to Definition R1, as follows:

\thbegin Definition Q1. {\sl A $b$-ary sequence of length $N$ is
``random'' if it is $k$-distributed (in the above sense) for all
positive integers $k ≤ \log↓b N$.}

\yyskip According to this definition, for example,
there are 170 nonrandom binary sequences of length 11:
$$\vcenter{\halign{#\qquad⊗#\qquad⊗#\qquad⊗#\cr
00000001111⊗10000000111⊗11000000011⊗11100000001\cr
00000001110⊗10000000110⊗11000000010⊗11100000000\cr
00000001101⊗10000000101⊗11000000001⊗10100000001\cr
00000001011⊗10000000011⊗01000000011⊗01100000001\cr
00000000111\cr}}$$
plus 01010101010 and all sequences with nine or more
zeros, plus all sequences obtained from the preceding sequences by
interchanging ones and zeros.

Similarly, we can formulate a definition for finite sequences
analogous to Definition R6. Let {\bf A} be a set of algorithms,
each of which is a combination selection and choice procedure
that gives a subsequence $\langle X↓s|infinf n\rangle ??R$,
as in the proof of Theorem M.

\thbegin Definition Q2. {\sl The $b$-ary sequence
X↓1$, $X↓2$, $\ldotss$, $X↓N$ is $(n, \epsilon )$-random with respect
to a set of algorithms} {\bf A}, {\sl if for every subsequence
X↓t|infinf 1, X↓t|infinf 2, . . , X↓t|infinf m determined by
an algorithm of} {\bf A} {\sl we have either m < n or}
$$|bigabs ${1\over m}$ \omega $↓a(X↓t|infinf 1, \ldotss , X↓t|infinf
m) - {1\over b} |bigabs ≤ \epsilon \qquad$ for\qquad $0 ≤ a
< b$.
|qctr \9skip Here $\nu ↓a(x↓1, \ldotss , x↓m)$ is the number
of $a$'s in the sequence $x↓1$, $\ldotss$, $x↓m$.

(In other words, ev ery sufficiently long subsequence determined
by an algorithm of {\bf A} must be approximately equi??distributed.)
The basic idea in this case is to let {\bf A} be a set of ``simple''
algorithms; the number (and the complexity) of the algorithms
in {\bf A} can grow as $N$ grows.

As an example of Definition Q2, let us consider binary sequences,
and let {\bf A} be just the following four algorithms:
$$\quad a) Take the whole sequence.

b) Take alternative terms of the sequence, starting with the
first.

c) Take the terms of the sequence following a zero.

d) Take the terms of the sequence following a one.

|qleft \12skip Now a sequence $X↓1$, $\ldotss$, $X↓8$ is $(4, {1\over
8})$-random if:
$$|indent by (a), |${1\over 8}$($X↓1 + \cdots + X↓8) - {1\over
2}| ≤ {1\over 8}$, if there are 3, 4, or 5 ones;

|qleft \6skip by (b), |${1\over 4}$($X↓1 + X↓3 + X↓5 + X↓7)
- {1\over 2}| ≤ {1\over 8}$, i.e., if there are two ones in
odd-numbered positions.

|qleft \6skip by (c), there are three possibilities depending
on how many zeros occupy positions $X↓1$, $\ldotss$, $X↓7$: if there
are 2 or 3 zeros here, there is no condition to test (since
$n = 4)$; if there are 4 zeros, they must be followed by two
zeros and two ones; and if there are 5 zeros, they must be followed
by two or three zeros.

|qleft \12skip |cancelindent by (d), we get conditions similar
to those implied by (c).

It turns out that only the following binary sequences of length
8 are (4, ${1\over 8}$)-random with respect to these rules:
$$00001011\qquad 00101001\qquad 01001110\qquad 01101000
|qctr 00011010\qquad 00101100\qquad 01011011\qquad 01101100
|qctr 00011011\qquad 00110010\qquad 01011110\qquad 01101101
|qctr 00100011\qquad 00110011\qquad 01100010\qquad 01110010
|qctr 00100110\qquad 00110110\qquad 01100011\qquad 01110110
|qctr 00100111\qquad 00111001\qquad 01100110\qquad \qquad \qquad
 |qctr \9skip plus those obtained by interchanging 0 and 1 consistently.

It is clear that we could make the set of algorithms so large
that no sequencex satisfy the definition, when $n$ and $\epsilon$
are reasonably small. A. N. Kolomogorov has proved that an $(n,
\epsilon )$-random binary sequence {\sl will} always exist,
for any given $N$, if the number of algorithms in {\bf A} does
not exceed
$$${1\over 2}e↑{2n|}≤e|supsup 2↑{(1-|}≤e↑).\eqno (35)$
|qctr \9skip This result is not nearly strong enough to show
that sequences satisfying Definition Q1 will exist, but the
latter can be constructed efficiently using the procedure of
Rees in exercise 3.2.2-21.

Still another interesting approach to a definition of randomness
has been taken by Per Martin-L|spose 4of [{\sl Information and
Control \bf 9} (1966), 602--619]. Given a finite $b$-ary sequence
$X↓1$, $\ldotss$, $X↓N$, let $??3(X↓1, \ldotss , X↓N)$ be the length
of the shortest Turing machine program which generates this
sequence. (For a definition of Turing machines, see Chapter
11; alternatively, we could use certain classes of effective
algorithms, such as those defined in exercise 1.1--8.) Then
??3($X↓1, \ldotss , X↓N)$ is a measure of the ``patternlessness''
of the sequence, and we may equate this idea with randomness.
The sequences of length $N$ which maximize $??3(X↓1, \ldotss
, X↓N)$ may be called random. (From the standpoint of practical
random-number generation by computer, this is, of course, the
worst definition of ``randomness'' that can be imagined!)

Essentially the same definition of randomness was independently
given by G. Chaitin at about the same time; see {\sl JACM \bf 16}
(1969), 145--159. It is interesting to note that even though
this definition makes no reference to equi??distribution properties
as our other definitions have, Martin-L|spose 4of and Chaitin
have proved that random sequences of this type also have the
expected equi??distribution properties. In fact, Martin-L|spose
4of has demonstrated that such sequences satisfy {\sl all} computable
statistical tests for randomness, in an appropriate sense.

subsectionbegin{F. Summary, history, and bibliography}
We have defined several degrees of randomness that a sequence
might possess.

An infinite sequence which is $∞$-distributed satisfies
a great many useful properties which are expected of random
sequences, and there is a rich theory concerning $∞$-distributed
sequences. (The exercises which follow develop several important
properties of $∞$-distriguted sequences which have not been mentioned
in the text.) Definition R1 is therefore an appropriate basis
for theoretical studies of randomness.

The concept of an $∞$-distributed $b$-ary sequence was introduced
in 1909 by Emile Borel. He essentially defined the concept of
an $(m, k)$-distributed sequence, and showed that the $b$-ary
representations of almost all real numbers are $(m, k)$-distributed
for all $m$ and $k$. He called such numbers {\sl normal} to
base $b$. An excellent discussion of this topic appears in his
well-known book, $Le|spose &cons sur la th|spose 1eorie des
fonctions$ (2nd ed., 1914), 182--216.

The notion of an $∞$-distributed sequence of {\sl real} numbers,
also called a {\sl completely equidistributed sequence,} was
introduced by N. M. Korobov in {\sl Doklady Akad.\ Nauk SSSR
\bf 62} (1948), 21--22. He and several colleagues developed
the theory of such sequences quite extensively during the 1950s
in a series of papers. The book {\sl Uniform Distribution of
Sequences} by L. Kuipers and H. Niederreiter (New York: Wiley,
1974) is an extraordinarily complete source of information about
the rich mathematical literature concerning $k$-distributed
sequences of all kinds.

We have seen, however, that $∞$-distributed sequences need not
be sufficiently haphazard to qualify completely as ``random.''
Three definitions, R4, R5, and R6, were formulated above to
provide the additional conditions; and Definition R6, in particular,
seems to be an appropriate way to define the concept of an infinite
random sequence. It is a precise, quantitative statement that
may well coincide with the intuitive idea of true randomness.
|qleft a????????????|newtype W58320---Computer
%folio 216 galley 9 (C) Addison-Wesley 1978	-
Historically, the development of these definitions was primarily
influenced by R. von Mises' quest for a good definition of ``probability.''
In {\sl Math.\ Zeitschrift \bf 5} (1919), 52--99, von Mises proposed
a definition similar in spirit to Definition R5, although stated
too strongly (like our Definition R3) so that no sequences satisfying
the conditions could possibly exist. Many people noticed this
discrepancy, and A. H. Copeland [{\sl Amer.\ J. Math.\ \bf 50}
(1928), 535--552] suggested weakening von Mises' definition
by substituting what he called ``admissible numbers'' (or Bernoulli
sequences). These are equivalent to $∞$-distributed $[0,1)$ sequences
in which all entries $U↓n$ have been replaced by 1 if $U↓n <
p$ or by 0 if $U↓n ≥ p$, for a given probability $p$. Thus Copeland
was essentially suggesting a return to Definition R1. Then Abraham
Wald showed that it is not necessary to weaken von Mises' definition
so drastically, and he proposed substituting a countable set
of subsequence rules. In an important paper [{\sl Ergebnisse
eines math.\ Kolloquiums \bf 8} (Vienna, 1937), 38--72], Wald
essentially proved Theorem W, although he made the erroneous
assertion that the sequence constructed by Algorithm W also
satisfies the stronger condition that $\Pr(U↓n \in A) =\hjust{measure
of }A$, for all Lebesgue measurable $A \subset $[0,1)$. We have
observed that no sequence can satisfy this property.

The concept of ``computability'' was still very much in its
infancy when Wald wrote his paper, and A. Church [{\sl Bull.\ Amer.\ Math.\
Soc.\ \bf 47} (1940), 130--135] showed how the precise notion
of ``effective algorithm'' could be added to Wald's theory to
make his definitions completely rigorous. The extension to Definition
R6 was due essentially to A. N. Kolmogorov [{\sl Sankhy\=a}
series A, {\bf 25} (1963), 369--376], who proposed Definition
Q2 for finite sequences in that same paper.

\def\\{{\sl Zeitschr.\ f.\ math.\ Logik und Grundlagen d.\ Math.\ }}
Another important contribution was made by Donald W. Loveland
[\\ {\bf12} (1966), 279--294], who discussed Definitions R4, R5, R6, and
several concepts in between. Loveland proved that there are
R5 = random sequences which do not satisfy R4, thereby establishing
the need for a stronger definition such as R6. In fact, he defined
a rather simple permutation $\langle f(n)\rangle$ of the nonnegative
integers, and an Algorithm W↑\prime analogous to Algorithm W,
such that \sqrt{Pr}($U↓{f(n)} ≥ {1\over 2}) $- Pr($U↓{f(n)}
≥ {1\over 2}) ≥ {1\over 2}$ for every R5 = random sequence $\langle
U↓n\rangle$ produced by Algorithm W↑\prime when it is given
an infinite set of subsequence rules ??R$↓k$. Schnorr's subsequent
book $Zuf|spose 4alligkeit und Wahrscheinlichkeit [Lecture Notes
in Math.\ \bf 218} (Berlin: Springer, 1971)] gives a much more
detailed treatment of the entire subject of randomness than
could be provided here and makes an excellent introduction to
the ever-growing advanced literature on the topic.

The publications of Church and Kolmogorov considered only binary
sequences for which $\Pr(X↓n = 1) = p$ for a given probability
$p$. Our discussion in this section has been slightly
more general, since a $[0,1)$ sequence essentially represents
all $p$ at once.

The von Mises--Church definition has been refined in
yet another interesting way by J. V. Howard, \\ {\bf21} (1975), 215--224.

In another paper [{\sl Problemy Pereda|spose ??3ci Inform acci
\bf 1} (1965), 3--11], Kolmogorov considered the problem of
defining the ``information content'' of a sequence, and this
work led to Chaitin and Martin-L|spose 4of's interesting definition
of finite random sequences via ``patternlessness.'' (See {\sl
IEEE Trans.\ \bf IT-14} (1968), 662--664.) Another definition
of randomness, somewhere ``between'' Definitions Q1 and Q2,
had been formulated many years earlier by A. S. Besicovitch
[{\sl Math.\ Zeitschrift \bf 39} (1934), 146--156].

For further discussion of random sequences, see K. R. Popper,
{\sl The Logic of Scientific Discovery (}London, 1959), especially
the interesting construction on pp. 162--163, which he first
published in 1934.

|qleft \24skip {\:r EXERCISES

\exno 1. [10] Can a periodic
sequence be equidistributed?

\exno 2. [10] Consider the periodic binary sequence 0, 0, 1,
1, 0, 0, 1, 1, $\ldotss\,$. Is it 1-distributed? Is it 2-distributed?
Is it 3-distributed?

\exno 3. [M22] Construct a periodic ternary sequence which is
3-distributed.

\exno 4. [HM22] Let $U↓n = (2↑|"l↑|πl↑{g(n+1)|}"L/3)$mod 1.
What is Pr($U↓n < {1\over 2})?$

\exno 5. [HM14] Prove that Pr\biglp $S(n)$ and T(n)\bigrp +
Pr\biglp $S(n)$ or $T(n)\bigrp =$ Pr\biglp $S(n)\bigrp +$ Pr\biglp
$T(n)\bigrp $, for any two statements $S(n), T(n)$, provided
at least three of the limits exist. [For example, if a sequence
is 2-distributed, we would find that
$$|newtype Pr($u↓1 ≤ U↓n < v↓1\qquad$ or\qquad $u↓2 |tab ≤ U↓{n+1}
< v↓2)⊗\4skip ⊗= v↓1 - u↓1 + v↓2 - u↓2 - (v↓1 - u↓1)(v↓2 - u↓2).]\cr

\exno 6. [HM23] Let $S↓1(n), S↓2(n), . .
$. be an infinite sequence of statements about mutually disjoint
events, i.e., $S↓i(n)$ and $S↓j(n)$ cannot simultaneously be
true if $i ≠ j$. Assume that Pr\biglp S$↓j(n)\bigrp exists for
each j ≥ 1$. Show that Pr\biglp $S↓j(n)$ is true for some $j
≥ 1\bigrp ≥ \sum ↓{j|}¬R↓1$ Pr\biglp $S↓j(n)\bigrp $, and give
an example to show that equality need not hold.

\exno 7. [HM27] As in the previous exercise, let $S↓{ij}(n),
i ≥ 1, j ≥ 1$, be infinitely many mutually disjoint events,
such that Pr\biglp $S↓{ij}(n)\bigrp$ exists. Assume that for
all $n > 0, S↓{ij}(n)$ is true for exactly one pair of integers
$i, j$. If \sum $↓{i,j|}¬R↓1$ Pr\biglp $S↓{ij}(n)\bigrp = 1$,
can it be concluded that, for all $i ≥ 1$, Pr\biglp $S↓{ij}(n)$
is true for some $j ≥ 1\bigrp$ exists and equals \sum $↓{j|}¬R↓1$
Pr\biglp $S↓{ij}(n)\bigrp ?$

\exno 8. [M15] Prove (13).

\exno 9. [HM20] Prove Lemma E.\xskip [{\sl Hint:} Consider $\sum
↓{1|}¬E↓{j|}¬E↓m (y↓{jn} - α)↑2.]$

\exno 10. [HM22] Where was the fact that $q$ is a multiple of
$m$ used in the proof of Theorem C?

\exno 11. [M10] Use Theorem C to prove that if $\langle U↓n\rangle$
is $∞$-distributed, so is the subsequence $\langle U↓{2n}\rangle
$.

\exno 12. [HM20] Show that a $k$-distributed sequence passes
the ``maximum of $k$'' test, in the following sense: Pr\biglp
$u ≤$ max($U↓n, U↓{n+1}, \ldotss , U↓{n+k-1}) < v\bigrp = v↑k
- u↑k$.

\exno 13. [HM27] Show that an $∞$-distributed $[0,1)$ sequence
passes the ``gap test'' in the following sense: If If 0 ≤ $α
< β ≤ 1$, and $p = β - α$, let $f(0) = 0$, and for $n ≥ 1$,
let $f(n)$ be the smallest integer $m > f(n - 1)$ such that
$α ≤ U↓m < β$; then Pr\biglp $f(n) - f(n - 1) = k\bigrp = p(1
- p)↑{k-1}$.

\exno 14. [HM25] Show that an $∞$-distributed sequence passes
the ``run test'' in the following sense: If $f(0) = 1$ and if
for $n ≥ 1 f(n)$ is the smallest integer $m > f(n - 1)$ such
that $U↓{m-1} > U↓m$, then
$$Pr\biglp $f(n) - f(n - 1) = \bigrp = 2k/(k + 1)! - 2(k + 1)/(k
+ 2)!$.

\exno 15. [HM30] Show that an $∞$-distributed
sequence passes the ``coupon-collector's test'' when there are
only two kinds of coupons, in the following sense` Let $X↓1,
X↓2, . . $. be an $∞$-distributed binary sequence. Let $f(0) =
0$, and for $n ≥ 1$ let $f(n)$ be the smallest integer $m >
f(n - 1)$ such that \{$X↓{f(n-1)+1}, \ldotss , X↓m\}$ is the
set \{0, 1\}. Prove that Pr\biglp $f(n) - f(n - 1) = k\bigrp
= 2↑{1-k}, k ≥ 2$. (Cf.\ exercise 7.)

\exno 16. [HM38] Does the coupon-collector's
test hold for $∞$-distributed sequences when there are more than
two kinds of coupons? (Cf.\ the previous exercise.)

\exno 17. [HM50] Given that $r$ is a rational number, Franklin
has proved that the sequence with $U↓n = (r↑n$ mod 1) is not
2-distributed. But is there any rational number $r$ for which
this sequence is equidistributed? In particular, is the sequence
equidistributed when $r = {3\over 2}?$ (Cf.\ the article by K.
Mahler, {\sl Mathematika \bf 4} (1957), 122--124.)

\exno 18. [HM22] Prove that if $U↓0, U↓1, . . $. is $k$-distributed,
so is the sequence $V↓0, V↓1, \ldotss $, where $V↓n = \lfloor
nU↓n\rfloor /n$.

\exno 19. [HM35] Consider Definition R4 with ``$∞$-distributed''
replaced by ``1-distributed''. Is there a sequence which satisfies
this weaker definition, but which is not $∞$-distributed? (Is
the weaker definition really weaker?)

\exno 20. [HM46] Does the sequence with $U↓n |newtype$ W58320---Computer
Programming\quad (Knuth/Addison-Wesley)\quad f. 220\quad ch.
%folio 220 galley 10 (C) Addison-Wesley 1978	-
\exno 21. [HM20] Let $S$ be a set and let ??M
be a collection of subsets of $S$. Suppose that $p$ is a real-valued
function of the sets in ??M, for which $p(M)$ denotes the probability
that a ``randomly'' chosen element of $S$ lies in $M$. Generalize
Definitions B and D to obtain a good definition of the concept
of a $k$-distributed sequence $\langle Z↓n\rangle$ of elements
of $S$ with respect to the probability distribution $p$.

\trexno 22. [HM30] (Hermann Weyl.)\xskip Show that the $[0,1)$ sequence
$\langle U↓n\rangle$ is $k$-distributed if and only if
$$\mathop{lim↓{|raise2 $N→∞} {1\over N} \sum ↓{0≤n<N}$ exp\biglp
$2πi(c↓1U↓n + \cdots + c↓kU↓{n+k-1})\bigrp = 0$
|qctr \6skip \3skip for every set of integers $c↓1$, $c↓2$, $\ldotss$,
$c↓k$ not all zero.

\exno 23. [M34] Show that a $b$-ary sequence $\langle X↓n\rangle$
is $k$-distributed if and only if all of the sequences $\langle
c↓1X↓n + c↓2X↓{n+1} + \cdots + c↓kX↓{n+k-1}\rangle$ are {\sl
equidistributed,} whenever $c↓1$, $c↓2$, $\ldotss$, $c↓k$ are integers
with $\gcd(c↓1, \ldotss , c↓k) = 1$.

\exno 24. [M30] Show that
a $[0,1)$ sequence $\langle U↓n\rangle$ is $k$-distributed if
and only if all of the sequences $\langle c↓1U↓n + c↓2U↓{n+1}
+ \cdots + c↓kU↓{n+k-1}\rangle$ are {\sl equidistributed,} whenever
$c↓1$, $c↓2$, $\ldotss$, $c↓k$ are integers not all zero.

\exno 25. [HM20] A sequence is called a ``white sequence'' if
all serial correlations are zero, i.e., if the equation in Corollary
S is true for {\sl all k ≥ 1. (}By Corollary S, an $∞$-distributed
sequence is white.) Show that if a $[0,1)$ sequence is equidistributed,
it is white if and only if
$$\mathop{lim↓{|raise2 $n→∞} {1\over n} \sum ↓{0≤j<n} (U↓j -
{1\over 2})(U↓{j+k} - {1\over 2}) = 0,\qquad$ all\qquad $k ≥
1$.

\exno 26. [HM34] (J. Franklin.)\xskip A
white sequence, as defined in the previous exercise, can definitely
fail to be random. Let $U↓0, U↓1, . . $. be an $∞$-distributed
sequence; define the sequence $V↓0, V↓1, . . $. as follows:
$$$(V↓{2n-1}, V↓{2n}) = (U↓{2n-1}, U↓{2n})\qquad$ if\qquad $(U↓{2n-1},
U↓{2n}) ε G$,
|qctr \4skip (V$↓{2n-1}, V↓{2n}) = (U↓{2n}, U↓{2n-1})\qquad$
if\qquad $(U↓{2n-1}, U↓{2n}) |spose ??ε G$,
|qctr \9skip where $G$ is the set \{($x, y) | x - {1\over 2}
≤ y ≤ x$ or $x + {1\over 2} ≤ y\}$. Show that\xskip (a) $V↓0, V↓1,
. . $. is equidistributed and white;\xskip (b) Pr($V↓n > V↓{n+1})
= {5\over 8}$. (This points out the weakness of the serial correlation
test.)

\exno 27. [HM49] What is the highest
possible value for Pr($V↓n > V↓{n+1}$- in an equidistributed,
white sequence? (D. Coppersmith [to appear] has constructed
such a sequence achieving the value ${7\over 8}$.)

\trexno 28. [HM21] Use the sequence
(11) to construct a $[0,1)$ sequence which is 3-distributed,
for which Pr($U↓{2n} ≥ {1\over 2}) = {3\over 4}$.

\exno 29. [HM34] Let $X↓0, X↓1, . . $. be a $(2k)$-distributed
binary sequence. Show that
$$\sqrt{Pr}($X↓{2n} = 0) ≤ {1\over 2} + \left({2k - 1\atop k}}\left/2↑{2k}$.

\trexno 30. [M39] Construct a binary
sequence which is $(2k)$-distributed, and for which
$$Pr($X↓{2n} = 0) = {1\over 2} + \left({2k - 1\atop k}}\left/2↑{2k}$.
|qctr \9skip (Therefore the inequality in the previous exercise
is the best possible.)

WHERE'S EX. 31?
\exno 32. [M24] Given that $\langle
X↓n\rangle$ is a ``random'' $b$-ary sequence according to Definition
R5, and if $??R$ is a computable subsequence rule which specifies
an infinite subsequence $\langle X↓n\rangle ??R$, show that
the latter subsequence is not only 1-distributed, it is ``random''
by Definition R5.

\exno 33. [HM24] Let $\langle U↓s|infinf
n\rangle$ and $\langle U↓s|infinf n\rangle$ be infinite disjoint
subsequences of a sequence $\langle U↓n\rangle $. (Thus, $r↓0
< r↓1 < r↓2 < \cdots$ and $s↓0 < s↓1 < s↓2 < \cdots$ are increasing
sequences of integers and $r↓m ≠ s↓n$ for any $m, n.)$ Let $\langle
U↓t|infinf n\rangle$ be the combined subsequence, so that $t↓0
< t↓1 < t↓2 < \cdots$ and the set \{$t↓n\} = \{r↓n\} ∪ \{s↓n\}$.
Show that if Pr($U↓r|infinf n ε A) =$ Pr($U↓s|infinf n ε A)
= p$, then Pr($U↓t|infinf n ε A) = p$.

\trexno 34. [M25] Define subsequence rules ??R$↓1, ??R↓2, ??R↓3,
. . . such that Algorithm W can be used with these rules to
give an effective algorithm to construct a $[0,1)$ sequence satisfying
Definition R1$.

\trexno 35. [HM35] (D. W. Loveland.)\xskip Show that if a binary sequence
$\langle X↓n\rangle$ is R5 = random, and if $\langle s↓n\rangle$
is any computable sequence as in Definition R4, we must have
\sqrt{Pr}($X↓s|infinf n = 1) ≥ {1\over 2}$ and Pr($X↓s|infinf
n = 1) ≤ {1\over 2}$.

\exno 36. [HM30] Let $\langle X↓n\rangle$ be a binary sequence
which is ``random'' according to Definition R6. Show that the
$[0,1)$ sequence $\langle U↓n\rangle$ defined in binary notation
by the scheme
$$$|tab U↓0 = 0.X↓0⊗\4skip ⊗U↓1 = 0.X↓1X↓2\cr
\4skip ⊗U↓2 = 0.X↓3X↓4X↓5\cr
\4skip ⊗U↓3 = 0.X↓6X↓7X↓8X↓9\cr
\2skip ⊗\cdots \cr
\9skip$ is random in the sense of Definition R6.

\exno 37. [M40] (D. Coppersmith.)\xskip
Define a sequence which satisfies Definition R4 but not Definition
R5.\xskip [{\sl Hint:} Consider changing $U↓0$, $U↓1$, $U↓4$, $U↓9$,
$\ldots$ in a truly random sequence.]
|qleft ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad
??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad
??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad
??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad